import java.util.List;

public class SortedListToBST {

    public TreeNode sortedListToBST(ListNode head) {
        if (head == null) return null;
        return dfs(head, null);
    }

    public TreeNode dfs(ListNode start, ListNode tail) {
        if (start == tail) return null;
        ListNode slow = start;
        ListNode fast = start;
        while (fast != tail && fast.next != tail) {
            fast = fast.next.next;
            slow = slow.next;
        }
        TreeNode node = new TreeNode(slow.val);
        node.left = dfs(start, slow);
        node.right = dfs(slow.next, tail);
        return node;
    }

    public TreeNode dfs1(int l, int r, List<Integer> list) {
        if (l == r) {
            return new TreeNode(list.get(l));
        }
        if (l < r) return null;
        int mid = (l + r) / 2;
        TreeNode node = new TreeNode(list.get(mid));
        node.left = dfs1(l, mid - 1, list);
        node.right = dfs1(mid + 1, r, list);
        return node;
    }
}
